package com.wtgroup.demo.leetcode.q005_最长回文子串;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/22 11:02
 */
public class S_Force {
    /*
    * 逐个长度尝试.
    * 子串长度 n , 每次长度 m , 子串内判断子串 m/2
    * => O(n^3)
    * */

    public String longestPalindrome(String s) {
        if (s.length()==0) {
            return "";
        }
        int n = s.length();
        int maxLen = 1; // 只要字符串非空, 第0号必然是
        int st = 0;

        for (int m = 1; m < n; m++) { // m 看看有没有 m+1 长度的回文串, 这里m是 i往后的偏移
            for (int i = 0; i < n-m; i++) { // i 观察回文串的开头
                // 判断 i~i+m 子串是否回文串
                boolean isPalind = true;
                for (int j = 0; j <= m / 2; j++) {
                    // 两边对称对比, 只要有一对不满足, 即说明不是回文串
                    if (s.charAt(i+j) != s.charAt(i + m - j)) {
                        isPalind = false;
                        break;
                    }
                }
                if (isPalind) {
                    st = i;
                    maxLen = m+1;
                    // 不用移到后面看了, 已经出现 m 长度的回文串
                    break;
                }
            }
        }

        String ans = s.substring(st, st + maxLen);
        return ans;
    }


    public static void main(String[] args) {
        // String in = "babad";
        // String in = "cbbd";
        // String in = "a";
        // String in = "ac";
        // System.out.println(new S_Force().longestPalindrome(in));

        String[] ss = {"babad", "cbbd", "a", "ac", "fgosujtgyeowsyhuermhldjhldrdlgjslgjfsaopyrtgujsdlhkjlsegjsl"};
        for (String s : ss) {
            System.out.println(new S_Force().longestPalindrome(s));
        }
    }

}
